package offer;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 * 剑指 Offer 39. 数组中出现次数超过一半的数字
 * </p>
 *
 * @author xiaozuolin
 * @date 2021/9/24 14:42
 */
public class Offer39 {
    //1.哈希表统计法
    public int hashStatistics(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (map.get(num) > (nums.length / 2)) {
                return num;
            }
        }
        return 0;
    }

    //2.数组排序法

    //3.摩尔投票法
    public int majorityElement(int[] nums) {
        int x = 0;
        int votes = 0;
        int count = 0;
        for (int num : nums) {
            if (votes == 0) {
                x = num;
            }
            votes += num == x ? 1 : -1;
        }
        //验证x的出现的次数是否超过数组个数的一半
        for (int num : nums) {
            if (num == x) {
                count++;
            }
        }
        return count > nums.length / 2 ? x : 0;
    }
}
